Quantum Circuit Design Using Genetic Algorithms

image.png

Motivation

Several applications in quantum computing, quantum information and quantum communication require the preparation of entangled quantum states such as the Bell state, the W state or the GHZ (Greenberger-Horne-Zeilinger) state. One can prepare these states by starting with some initial quantum state and applying quantum gates on this state until the target state is reached. This sequence of quantum gates that transform a given initial state to some final state is referred to as a quantum circuit.

Constructing quantum circuits which prepare the required state is often a difficult task. Traditionally, the circuits were designed by hand, using a combination of trial and error and accumulated experience to identify design patterns and reusable units from previously made circuits. This process is often tedious and very hard to do for all but the simplest of circuits. Furthermore, such a manually constructed circuit is not guaranteed to be the most efficient circuit (i.e. of the lowest circuit depth) which achieves the task.

This is where classical optimization algorithms enter the picture. One may use these algorithms to search the space of possible circuits (subject to some constraints) and identify the circuit which most efficiently produces the required quantum state. There are several approaches to performing such optimization. Of these, the approach we used in this project is genetic algorithms.

Overview of Genetic Algorithms

image.png *Designed by pch.vector / Freepik

Genetic algorithms are a class of optimization algorithms that are named so because they draw inspiration from core concepts of genetics and evolutionary biology. Consider this highly simplified description of the typical process of evolution of a species: The most fit individuals of the population mate with each other to produce the next generation of individuals. This process involves combining the DNA of both parents to form the DNA of the offspring. However, in addition to this recombination, there are random mutations which take place. Mutations that are favorable to the survival of offspring get passed on to latter generations. In this way, subsequent generations end up having more favorable traits (i.e. they are "fitter") compared to previous generations. To summarize, the ingredients of evolution are:

  1. Reproduction
  2. Genetic crossover
  3. Random mutations
  4. Natural selection

Genetic algorithms follow the same structure. Given a problem:

  1. We start with a population of candidate solutions to the problem, where individual members of the population are often encoded as some array of values which is often referred to as the genome, called so because it plays the same role here as its biological namesake.
  2. We define a fitness function to determine the quality (or "fitness") of the solution. Then, we select the fittest members of the population to create the next generation. This is the selection step of the algorithm.
  3. To create "offspring" solutions from "parent" solutions, we perform a crossover. That is, we splice the strings representing the genomes of the parents and recombine them. This crossover is supposed to emulate the genetic recombination that takes place during sexual reproduction.
  4. After the crossover, the genomes are modified at random locations to model mutation.
  5. This process is then repeated over several generations until the fitness of the individuals converges to some value (which hopefully maximizes the fitness function).

The general algorithm can be summarized as follows - image.png

It was shown in recent papers [1, 2] that this approach can be used to produce circuits to generate the state which use fewer gates and have a lower circuit depth. Since we are in the NISQ era, current quantum devices are noisy and having less circuit depth helps to reduce the total error accrued in state preparation.

[1] Creevey, Floyd M., Charles D. Hill, and Lloyd CL Hollenberg. "GASP--A Genetic Algorithm for State Preparation." arXiv preprint arXiv:2302.11141 (2023).

[2] Sünkel, Leo, et al. "GA4QCO: Genetic Algorithm for Quantum Circuit Optimization." arXiv preprint arXiv:2302.01303 (2023).

Before we move on to the specifics of the problem and our approach to solving it, it is worth mentioning that organisms can reproduce asexually as well, which would mean a process with all the steps above except for the crossover step. Indeed, genetic algorithms can be designed without the crossover step [3] and this has advantages in some situations. However, in most cases, crossover plays an important role in ensuring effective optimization and our approach makes use of the crossover step.

[3] Sadegh Salesi, Georgina Cosma, Michalis Mavrovouniotis. "TAGA: Tabu Asexual Genetic Algorithm embedded in a filter/filter feature selection approach for high-dimensional data"

Problem Setup

The initial and final quantum states are specified in advance and our task is to determine a quantum circuit(s) which performs the required transformation from the initial state to the final state. We want our quantum circuit to have as low a circuit depth as possible.

Problem solution

To implement the genetic algorithm, we begin by making the following correspondence between our problem and the general structure of the algorithm:

Genetic algorithm Our Problem
Population Collection of all candidate circuits
Individual of a population One candidate circuit
Gene Any given gate of a given circuit
Genome Set of gates of any circuit

We start with defining the quantum device, the number of qubits on the chip, and the basis set of gates. To be consistent with [1], we define the single qubit rotation gate set and the CNOT gate as the basis gates in our circuit. In other words, the genome of any circuit is comprised of these gates only.

1. Generating a random circuit

To generate an initial population of individuals, we randomly select gates (with random parameters) from the basis gates set.

For example a random circuit with 5 gates would be something like -

2. Assess the fitness of the population

Next we assess the fitness of the population. The fitness of any individual circuit is calculated as the inner product of the target state with the state obtained from the circuit. $$ F = |\langle \psi_{Target} | U_{Circuit}| 0 \rangle|^2 $$

This makes intuitive sense since this function F simply measures the square of the overlap between the produced state and the target state. If F=1, then the target state has been produced. Hence, our goal is to eventually produce a circuit such that its fitness function is as close to 1 as possible.

3. Offsprings - Crossover and Mutation

image.png

*Healthcare and medical icons created by Freepik - Flaticon

If by some stroke of good fortune, there were to be an individual in the generated population that has the required fitness, our algorithm would terminate (the precise termination criterion is quantified later in the notebook). However, this is a very unlikely scenario. Hence, we shall now introduce variability in our population using crossover and mutation. The aim is that under selection pressure (that we are imposing through the fitness function we defined above), this effect of crossover and mutation is to produce new generations which are fitter than the ones we started out with.

Crossover between two individuals is the process in which the offsprings of two individuals carry part of their genes from one parent and others from other parent. We implement a single-point crossover in our code. By this, we mean that one half of the offspring's genes are from one parent and other half from the other parent. More precisely, we build new circuits by merging half of one parent circuit with the other half of the other parent circuit.

Mutation is the process in which some of the genes of an individual are changed with some probability. Here we modify the gates in the circuit with some probability p.

Crossover and mutation, like natural evolution, brings variability in the circuit and helps to search the parameter space of the problem. Additionally, Mutation and crossover add randomization to the circuit and make sure that the solutions are not stuck in a local minima.

An example of crossover would be - (the first two represent parent individuals and the last two represent offsprings)

4. Optimizing the individuals

Next, we optimize the parameters (i.e., angles of the rotation gates) of the new individuals created to maximize the fitness of the population. This optimization is done using the pennylane's Adam optimizer.

Having optimized the parameters, we choose the top n fittest individuals of the population to serve as parents to the next generation.

The steps of this algorithm are summarized by the following flowchart:

image.png

5. Running the algorithm

Here we iterate the above steps with a given number of gates in the circuit. If we reach MAX_ITER number of steps and we don't have a solution, then we increase the number of gates in the circuit by 1 and repeat the process.

6. Process results

Results

1. T-gate Magic state

We start with the simplest circuit, involving only one qubit and single qubit rotation gates. We try to find a circuit that can produce the magic state that can be used to implement T-gates using gate teleportation. Magic states were introduced by Bravyi and Kitaev [3] and are essential to creating a universal gate set.

The T-gate magic state is given by $|T_0\rangle = cos(\beta)|0\rangle + e^{i\frac{\pi}{4}} sin(\beta) |1\rangle$

Choosing $\beta = \frac{\pi}{3}$

Here we start the circuits with only one gate initially and let the algorithm figure out circuits that can produce the T-gate magic state.

[3] Bravyi, Sergey, and Alexei Kitaev. "Universal quantum computation with ideal Clifford gates and noisy ancillas." Physical Review A 71.2 (2005): 022316.

The above outputs are the circuits proposed by the genetic algorithm to prepare the given target state.

2. Bell state $|\Phi^+\rangle$

Increasing the complexity a bit, we move to two qubits, and try to produce entangled states. An very important example of the two qubit entangled state are the Bell states or the EPR pairs. Bell states are a set of maximally entangled states and are useful for superdense coding and quantum teleportation.

The Bell state $|\Phi^+\rangle$ is given by - $$ |\Phi^+\rangle = \frac{1}{\sqrt{2}} (|00\rangle + |11\rangle) $$

The above output is a circuit proposed by the genetic algorithm to prepare the given target state.

3. Bell State $|\Phi^-\rangle$

Next we try to find a circuit to construct the $|\Phi^-\rangle$ state. It is given by - $$ |\Phi^-\rangle = \frac{1}{\sqrt{2}} (|00\rangle - |11\rangle) $$

The above output is a circuit proposed by the genetic algorithm to prepare the given target state.

4. 3-Qubit GHZ state

A generalization of the Bell states are the GHZ states (Greenberger–Horne–Zeilinger states). These are a set of maximally entangled states for higher qubit numbers. We try to design the circuit to produce a 3-Qubit GHZ state: $$ |GHZ\rangle = \frac{1}{\sqrt{2}}(|000\rangle + |111\rangle) $$

GHZ state can be used to correct 3 Qubit bit flip errors using a 3-Qubit error correcting code.

The above output is a circuit proposed by the genetic algorithm to prepare the given target state.

5. 3-Qubit W state

As shown by Wolfgang Dür, Guifré Vidal and Ignacio Cirac [4] that there are two inequivalent types of 3-Qubit maximally mixed states - the GHZ state and the W state. The W state is given by: $$ |W\rangle = \frac{1}{\sqrt{3}}(|001\rangle + |010\rangle + |100\rangle) $$

The standard circuit to generate a W state is given by

image.png

This circuit contains a controlled Hadamard gate. Our circuit only uses single qubit rotation gates and CNOT gates to produce the same state.

This shows that this algorithm can also be use for quantum circuit compilation and can produce equivalent circuits for many circuits containing controlled unitary gates, which are hard to implement experimentally.

[4] Dür, Wolfgang, Guifre Vidal, and J. Ignacio Cirac. "Three qubits can be entangled in two inequivalent ways." Physical Review A 62.6 (2000): 062314.

The above output is a circuit proposed by the genetic algorithm to prepare the given target state.

Looking Ahead

We implemented a variant of the GASP algorithm and designed quantum circuits to prepare the T-gate magic state, Bell state, 3-qubit GHZ state and the 3-qubit W state. We saw that multiple equivalent circuits exist which produce the same target state. Our work can be used to achieve quantum circuit compilation, wherein we decompose complex unitaries into simpler basis gates (i.e. CNOT gates and single qubit rotations).

A possible direction for future work is to adapt the current approach to noisy gates in order to design efficient circuits for today's NISQ era.